package com.yun.datastructure.tree.binarytree.leetcode;

import com.yun.datastructure.tree.binarytree.domain.TreeNode;

public class Leetcode105 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return split(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }

    private TreeNode split(int[] preorder, int[] inorder, int ph, int pt, int ih, int it) {
        if (ph == pt) {
            return new TreeNode(preorder[ph]);
        }
        if (ph > pt) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[ph]);
        int sp = 0;
        for (int i = ih; i <= it; i++) {
            if (inorder[i] == preorder[ph]) {
                break;
            }
            sp++;
        }
        root.left = split(preorder, inorder, ph + 1, ph + sp, ih, ih + sp);
        root.right = split(preorder, inorder, ph + sp + 1, pt, ih + sp + 1, it);
        return root;
    }
}
